import math

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 1:
            return 0

        isPrime = [True] * n
        isPrime[1] = False
        res = 0
        limit = int(math.sqrt(n))

        for i in range(2, limit + 1):
            if isPrime[i]:
                for j in range(i * i, n, i):
                    isPrime[j] = False

        for i in range(1, n):
            if isPrime[i]: res += 1

        return res


s = Solution()
print(s.countPrimes(10))
